const Stack = require('./stack')

const priorityMap = {
  '+': 1,
  '-': 1,
  '*': 2,
  '/': 2,
}

function infixExpToPostfixExp(exp) {
  const stack = new Stack()

  const postFixList = []
  for (let i = 0; i < exp.length; i++) {
    const item = exp[i]
    if (!isNaN(item)) {
      // 如果他是数字，直接放进 list 中
      postFixList.push(item)
    } else if (item === '(') {
      // 遇到左括号，则入栈
      stack.push(item)
    } else if (item === ')') {
      // 如果遇到右括号，则遍历栈中所有运算符，并添加到 list 中，直到遇到左括号停止添加
      while (stack.top() !== '(') {
        postFixList.push(stack.pop())
      }
      // 弹出左括号
      stack.pop()
    } else {
      // 如果为运算符则看看栈中是否为空
      // 如果为空，则不循环直接添加栈中。
      // 如果不为空，则循环判断运算符优先级是否小于栈中的运算符，如果栈中运算符优先级大于等于当前的运算符，这出栈并添加到 list 中。直到栈中运算符比当前小于等于
      while (
        !stack.isEmpty() &&
        ['+', '-', '*', '/'].indexOf(stack.top()) >= 0 &&
        priorityMap[stack.top()] >= priorityMap[item]
      ) {
        postFixList.push(stack.pop())
      }
      // 将当前的运算符入栈
      stack.push(item)
    }
  }

  while (!stack.isEmpty()) {
    postFixList.push(stack.pop())
  }

  return postFixList
}

const test1 = ['12', '+', '3'] // 12+3
const test2 = ['2', '-', '3', '+', '2'] // 2-3+2
const test3 = ['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '-', '3', ')', '+', '(', '9', '+', '8', ')'] // (1+(4+5+3)-3)+(9+8)

console.log(infixExpToPostfixExp(test1))
console.log(infixExpToPostfixExp(test2))
console.log(infixExpToPostfixExp(test3))
